/*************************************************************************
	> File Name: 003.HuffmanTree.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 一 10/11 22:52:26 2021
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//Huffman树是完全二叉树

//二叉树节点定义
typedef struct Node {
    char ch;
    double frequency;
    struct Node *next[2];
} Node;

//每个字符出现的频次
typedef struct Data {
    char ch;
    double frequency;
} Data;


//编码
typedef struct Code {
    char ch; //对ch字符进行编码
    char *str; //编码后的字符串
} Code;

typedef struct Huffman_Tree {
    Node *root;
    int n;
    Code *codes;
} Huffman_Tree;

#define max_n 1000 

Data arr[max_n + 5];

Node *getNewNode(Data *obj) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->ch = (obj ? obj->ch : 0);
    p->frequency = (obj ? obj->frequency : 0);
    p->next[0] = p->next[1] = NULL;
    return p;
}

Huffman_Tree *getNewTree(int n) {
    Huffman_Tree *tree = (Huffman_Tree *)malloc(sizeof(Huffman_Tree));
    tree->root = NULL;
    tree->n = n;
    tree->codes = (Code *)malloc(sizeof(Code) * n);
    return tree;
}

/*
 * 插入排序
 */
void insert_sort(Node **arr, int i) {
    Node *tmp = arr[i];
    int j;
    for (j = i; j > 0 && arr[j - 1]->frequency < tmp->frequency; j--) {
        arr[j] = arr[j - 1];
    }
    arr[j] = tmp;
    return ;
}

/*
 * 获取编码
 */
//k表示添加到数组的哪个位置，level 表示访问到哈夫曼树的第几层
int extract_codes(Node *root, Code *arr, int k, int level, char *buff) {
    buff[level] = 0;
    //遍历时，往左走为0，往右走为1
    if (root->next[0] == NULL && root->next[1] == NULL) {
        arr[k].ch = root->ch;
        arr[k].str = strdup(buff);
        return 1;
    }
    int delta = 0;
    buff[level] = '0';
    delta += extract_codes(root->next[0], arr, k + delta, level + 1, buff);
    buff[level] = '1';
    delta += extract_codes(root->next[1], arr, k + delta, level + 1, buff);
    return delta;
}

/*
 * 构建哈夫曼树
 */
Huffman_Tree *build(Data *arr, int n) {
    Node **nodes = (Node **)malloc(sizeof(Node *) * n);

    //每个字符封装为结点，记录结点地址，传入arr[i]的地址
    for (int i = 0; i < n; i++) nodes[i] = getNewNode(arr + i);

    //频次从高到低进行排序(插入排序)
    for (int i = 1; i < n; i++) insert_sort(nodes, i);
    
    //从最后两位取数据构建哈夫曼树
    for (int i = n - 1; i >= 1; i--) {
        Node *p = getNewNode(NULL);
        p->next[0] = nodes[i - 1]; //倒数第二个作为左孩子
        p->next[1] = nodes[i]; //倒数第一个为右孩子
        p->frequency = nodes[i - 1]->frequency + nodes[i]->frequency;
        nodes[i - 1] = p;//合并后的数据插入到原数组中
        insert_sort(nodes, i - 1);
    }
    char *buff = (char *)malloc(sizeof(char *) * n);
    Huffman_Tree *tree = getNewTree(n);
    tree->root = nodes[0];
    extract_codes(tree->root, tree->codes, 0, 0, buff); //打印编码，编码左边为0，右边为1
    free(nodes);
    free(buff);
    return tree;
}


int main() {
    int n; //对n个字符进行编码
    scanf("%d", &n);
    char str[10];
    for (int i = 0; i < n; i++) { 
        //%c读入可能会出现参数读入错误的情况，于是使用%s读入
        scanf("%s%lf", str, &arr[i].frequency);
        arr[i].ch = str[0];
    }
    Huffman_Tree *tree = build(arr, n);
    for (int i = 0; i < tree->n; i++) {
        printf("%c ：%s\n", tree->codes[i].ch, tree->codes[i].str);
    }
    return 0;
}
